\begin{definition}
  $x$ --- \textit{двухсторонний нуль}\index{Двухсторонний нуль},
  если он одновременно и левый нуль, и правый.
\end{definition}

\begin{category}
  Пусть $M$ --- множество (будем называть его множеством \textit{слов}),
  $\Sigma$ --- некоторое исчисление.

  Последовательность $(\alpha=\alpha_1,\alpha_2,\ldots,\alpha_n=\beta)$
  называется \textit{доказательством} $\beta$ из $\alpha$. Введём
  категорию:
    $$\mathrm{Ob}C=M$$
    $$C(\alpha,\beta)\qquad \text{--- множество доказательств $\beta$ из $\alpha$}$$ 
    $$I(\alpha)=(\alpha)$$
 
  Введём обозначение для стрелок в этой категории: $\alpha\vdash_{\Sigma}^A\beta$.

  Если $\alpha\vdash_{\Sigma}^A\beta$ и $\beta\vdash_{\Sigma}^B\gamma$,
  то $A\circ B$ --- это конкатенация двух последовательностей доказательств
  без дублирующейся $\beta$.
\end{category}

\begin{exercise}Это категория.\end{exercise}

\begin{category}
  $\mathrm{Ob}C$ --- типы данных, $\mathrm{Mor}C$ --- программы.

  Запись $u\xrightarrow{\alpha} v$ означает, что программа $\alpha$
  получает на вход данные типа $u$ и возвращает данные типа $v$. 

  $1_u$ --- программа, которая не меняет входные данные.
\end{category}

\begin{category}
  $\mathrm{Ob}C$ --- состояния, $\mathrm{Mor}C$ --- тройки $(u,v,\alpha)$,
  где $u,v\in\mathrm{Ob}C$

  Запись $u\xrightarrow{\alpha} v$ означает, что программа $\alpha$
  может перевести $u$ в $v$.
  
  $1_u\leftrightharpoons (u,u,\{u\})$
\end{category}

\begin{category} (\textit{Дискретная категория}\index{Категория дискретная})
  
  Пусть $X$ --- некоторое множество.
  Тогда $\mathrm{Dis}(X)$ --- дискретная категория на нём.

  Если $C=\mathrm{Dis}(X)$, то
    $$\mathrm{Ob}C=X,\quad \mathrm{Mor}C=X,\quad 1_x=x,\quad x\circ x=x$$

  Эта категория является минимальной в том смысле, что в ней нет подкатегорий,
  получающихся только выкидыванием морфизмов.
\end{category}

\begin{definition}
  $C/\approx_C$ называют множеством \textit{кластеров}\index{Кластер}
  (или \textit{сгустков}\index{Сгусток}).
\end{definition}

\begin{category}\label{quasiascat}
  Пусть дана пара множеств $(W,R)$ такая, что $W\ne\emptyset$,
  $R\subseteq W\times W$, $R$
  рефлексивно\footnote{Т.е. $\forall x\in W\; (x,x)\in R$} и
  транзитивно\footnote{Т.е. $\forall (x,y)\in R\; \forall (y,z)\in R\;
                             (x,z)\in R)$}.

  Такую пару множеств мы будем называть \textit{квазипорядком}\index{Квазипорядок}.

  Тогда $\mathrm{Cat}(W,R)$ --- это такая категория $C$, что
  $$\mathrm{Ob}C\leftrightharpoons W$$
  $$C(u,v)\leftrightharpoons \begin{cases}
             \{(u,v)\},&\mbox{если $(u,v)\in R$}\\
             \emptyset,&\mbox{если $(u,v)\notin R$}
           \end{cases}$$

  По определению $1_u=(u,u)$ и оно существует, т.к. $R$ рефлексивно.

  По определению $(u,v)\circ(v,w)$ может быть равно только $(u,w)$, а
  $(u,w)\in R$, т.к. $R$ --- транзитивно.

  Видно, что $\mathrm{Cat}(W,=_W)=
      \mathrm{Dis}(W)$\footnote{$=_W\leftrightharpoons \{(x,x)\mid x\in W\}$}.

  Свойства категории $C=\mathrm{Cat}(W,R)$:
  \begin{enumerate}
    \item $|C(x,y)|\leq 1$ \\
    \item Если $\forall v\in W: uRv$, то $u$ --- начальный элемент в $C$. \\
    \item Все начальные элементы лежат в одном кластере и только они в этом
          кластере. \\
  \end{enumerate}

\end{category}

\begin{definition}
  \textit{Функтор}\index{Функтор} $F$ категории $C$ на категорию$D$ ---
   это пара $(F_0,F_1)$, где $F_0\colon \mathrm{Ob}C\to \mathrm{Ob}D$,
   $F_1\colon \mathrm{Mor}C\to \mathrm{Mor}D$, со свойствами:
   \begin{enumerate}
     \item $x\xrightarrow{\alpha} y \Rightarrow
            F_0(x)\xrightarrow{F_1(\alpha)} F_0(y)$\\
     \item $F_1(1_x)=1_{F_0(x)}$\\
     \item $x\xrightarrow{\alpha} y\xrightarrow{\beta} z \Rightarrow
            F_1(\alpha\circ\beta)=F_1(\alpha)\circ F_1(\beta)$\\
   \end{enumerate}

   Вместо $F_0$ и $F_1$ мы будем писать просто $F$.

   Обозначение для функтора: $F\colon C\rightsquigarrow D$.
\end{definition}

\begin{definition}
  Функтор $F$ называется \textit{изоморфизмом}\index{Изоморфизм}
  категорий, если $F_0$ и $F_1$ --- биекции.
\end{definition}

\begin{lemma}
  Всякий функтор $F$ с биективным $F_1$ является изоморфизмом. 
\end{lemma}

\begin{exercise}Докажите лемму.\end{exercise}

\begin{definition}
  Если между категориями $C$ и $D$ существует изоморфизм $F$, то будем говорить,
  что эти категории \textit{изоморфны}\index{Категории изоморфные} и писать
  $C\approx D$.
\end{definition}

\begin{functor} (\textit{Тождественный функтор}\index{Функтор тождественный})
  
  $$1_C\colon C\approx C$$
\end{functor}

\begin{functor} (\textit{Функтор включения}\index{Функтор включения})

   Если $C\subseteq D$, то введём функтор $F\colon C\rightsquigarrow D$:
     $$\forall x\in \mathrm{Ob}C\quad F_0(x)\leftrightharpoons x$$
     $$\forall \alpha\in \mathrm{Mor}C\quad F_1(\alpha)\leftrightharpoons \alpha$$
\end{functor}

\begin{lemma}[Упражнение]
  $\approx$ задаёт отношение эквивалентности на классе категорий.
\end{lemma}

\begin{lemma}
  Пусть $C$ --- малая категория со следующими свойствами:
  \begin{enumerate}
    \item $\forall x\in \mathrm{Ob}C\quad C(x,x)={1_x}$\\
    \item $x\ne y \Rightarrow C(x,y)=\emptyset$\\
  \end{enumerate}
  тогда $C\approx \mathrm{Dis}(\mathrm{Ob}C)$.
\end{lemma}

\begin{proof}
  $X\leftrightharpoons\mathrm{Ob}C$, $F(x)\leftrightharpoons x$, $F(1_x)\leftrightharpoons x$

  Проверяем, что $F$ --- это действительно функтор:
    $$F(1_x\circ 1_x)=F(1_x)=x=x\circ x=F(1_x)\circ F(1_x)$$
\end{proof}

\begin{lemma}
  Пусть $C$ --- категория, $\forall x, y\in \mathrm{Ob}C\quad |C(x,y)|\leq 1$.

  Тогда существует квазипорядок $(W,R)$ такой, что $C\approx \mathrm{Cat}(W,R)$.
\end{lemma}

\begin{proof}
  $W\leftrightharpoons \mathrm{Ob}C$, $xRy\leftrightharpoons C(x,y)\ne \emptyset$

  \begin{enumerate}
    \item Заметим, что $(W,R)$ --- квазипорядок. \textit{Упражнение}\\
    \item Построим функтор $F\colon C\rightsquigarrow \mathrm{Cat}(W,R)$
       $$F(x)\leftrightharpoons x$$
       $$x\xrightarrow{\alpha} y \quad\Rightarrow\quad
                           F(\alpha)\leftrightharpoons (x,y)$$
       \textit{Упражнение}. Доказать, что $F$ --- функтор.\\
    \item Осталось убедиться в том, что $F$ --- это изоморфизм,
          т.е. проверить, что отображение на морфизмах является биекцией. Это
          очевидно по построению.
  \end{enumerate}
\end{proof}

\begin{definition}
  Если $C$ --- категория из предыдущей леммы, то
  $\mathrm{FR}(C)\leftrightharpoons(W,R)$ называется
  \textit{фреймовым представлением}\index{Фреймовое представление}.
\end{definition}

\begin{definition}
  \textit{Моноид} --- полугруппа с единицей.\footnote{
     Т.е. такая тройка $(G,\bullet,e)$, где $G$ --- множество,
     $\bullet$ --- ассоциативный бинарный оператор на нём, а $e\in G$ такой
     элемент, что $\forall a\in G\quad e\bullet a=a\bullet e=a$.}
\end{definition}

\begin{category}\label{monoidascat}
  Если $(G,\bullet,e)$ --- моноид, то введём категорию $C=Cat(G,\bullet,e)$:
  $$\mathrm{Ob}C=\{\star\}$$
  $$\mathrm{Mor}C=G$$
  $$1_{\star}\leftrightharpoons e$$
  $$a\circ b\leftrightharpoons a\bullet b$$
\end{category}

\begin{lemma}
Пусть $C$ --- малая категория с одним объектом.
Тогда $C\approx Cat(G,\bullet,e)$ для некоторого моноида $(G,\bullet,e)$.
\end{lemma}

\begin{proof}
  Пусть $x\in \mathrm{Ob}C$ --- единственный объект категории $C$.
  $$G\leftrightharpoons\mathrm{Mor}C,\quad
     \bullet\leftrightharpoons\circ,\quad
     e\leftrightharpoons 1_x$$
  $$F(x)\leftrightharpoons e,\quad F(\alpha)\leftrightharpoons \alpha$$
  \begin{exercise}Доказать $(G,\bullet,e)$ --- моноид,
         а $F$ --- изоморфизм.\end{exercise}
\end{proof}

\begin{exercise}
  Доказать $\mathrm{SET}\not\approx\mathrm{SET}^{\circ}$
\end{exercise}

\begin{category} (<<Категория треугольников>>) \label{trianglecat}

  Если $C$ --- категория, то для любого $a\in \mathrm{Ob}C$
  запись $C\downarrow a$ будет означать такую категорию $D$,
  что
    $$\mathrm{Ob}D\leftrightharpoons 
         \{\alpha\in \mathrm{Mor}C\mid t(\alpha)=a\}$$
    $$\mathrm{Mor}D\leftrightharpoons
         \{(\alpha,\beta,\gamma)\mid \alpha,\beta,\gamma\in\mathrm{Mor}C,\;
                                     t(\alpha)=a,\;
                                     t(\beta)=a,\;
                                     %t(\gamma)=a,\;
                                     \alpha=\gamma\circ\beta\}$$
  
    \begin{tikzcd}
      x \arrow{rr}{\gamma} \arrow{rd}{\alpha}&& y\arrow{ld}{\beta}\\
      &a&
    \end{tikzcd}
\end{category}

\begin{exercise} Построить функтор
              $F\colon C\downarrow a\rightsquigarrow C$.\end{exercise}

% TODO
%\begin{category} (<<Категория квадратов>>)
%  $C^{\to}$ ---
%\end{category}

\begin{functor}
  Пусть $C$ --- категория, построим функтор
  $\mathrm{HOM}_C(a,-): C\rightsquigarrow \mathrm{SET}$.

  Обозначим для простоты $F=\mathrm{HOM}_C$.
  $$F(x)\leftrightharpoons C(a,x)$$
  $$\forall x\xrightarrow{\alpha} y\quad F(\alpha): C(a,x)\to C(a,y)$$
  $$F(\alpha)(\beta)\leftrightharpoons \beta\circ\alpha$$
    \begin{tikzcd}
      x\arrow{rr}{\alpha}&& y\\
      & a \arrow{lu}{\beta} \arrow{ru}[description]{\beta\circ\alpha}&\\
    \end{tikzcd}
    \begin{tikzcd}
      &y \arrow{rd}{\alpha'} &\\
      x \arrow{ru}{\alpha} && z\\
      & a\arrow{lu}{\beta} \arrow{uu}[description]{\beta\circ\alpha}
         \arrow{ru}[description]{(\beta\circ\alpha)\circ\alpha'}
    \end{tikzcd}
    $$(F(\alpha')\circ F(\alpha))(\beta)=
      F(\alpha')\circ(F(\alpha)(\beta))=
      F(\alpha')(\beta\circ\alpha)=$$
    $$=(\beta\circ\alpha)\circ \alpha'=
      \beta\circ (\alpha\circ\alpha')=
      F(\alpha\circ\alpha')(\beta)$$

  Заодно введём двойственный $\mathrm{HOM}$-функтор:
    $$\mathrm{HOM}_C(-,a)\leftrightharpoons \mathrm{HOM}_{C^{\circ}}(a,-)$$
\end{functor}
